COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00012 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A81.Tex[358,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 30, 1988}
\leftline{\sevenrm Unpublished draft}
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\def\xeq{\buildrel \times\over =}%x over = 
\def\xleq{\buildrel \times\over ≤}%x over ≤ 
\def\xgeq{\buildrel \times\over ≥}%x over ≥ 

\bigskip
\noindent{Randomness Theorems}

\bigskip
\noindent{\bf Theorem A.} If $f$ is an unbounded non-decreasing recursive
function, and $S$ is an infinite sequence of bits, $S$ has infinitely
many prefixes $S↓L$ of length~$L$ and complexity $≤L+f(L)$.

\smallskip\noindent
{\bf Proof}. Construct (using the recursion theorem) a machine $M$ 
with program $\pi↓M$ which, on input
$0↑i1\,S↓{f↑{-1}(|\pi↓M|+i+1)}$, 
prints $S↓{f↑{-1}(|\pi↓M|+i+1)}$. Then
$$U(\pi↓M\,0↑i\,1\,S↓{f↑{-1}(|\pi↓M|+i+1)})=S↓{f↑{-1}(|\pi↓M|+i+1)}\,$$
and, letting $L=f↑{-1}(|\pi↓M|+i+1)$ for any $i$, $C(S↓L)≤f(L)+L$.

\smallskip
Examples: $f$ can be $\lg$, $\lg↑{\ast}$, or even the inverse of
Ackermann's function, so there is no effective way to separate the
complexities of prefixes from their lengths.

\smallskip\noindent
{\bf Lemma:} If $f$ is a recursive function,
$$P(x)\xgeq \sum\{\,P(y)\mid f(y)=x\,\}\,.$$

\smallskip\noindent
{\bf Proof:} Let $M$, on input $S$, compute $f\bigl(U(s)\bigr)$.
The probability that $U$ will compute $x$ is at least $2↑{-|\pi↓M|}$
times the sum, over all~$y$, of the probability that $U(s)=y$
and $f(y)=x$; i.e., $P(x)≥2↑{-|\pi↓M|}\sum\{\,P(y)\mid f(y)=x\,\}$.

\smallskip\noindent
{\bf Lemma:} If $r>0$, $1-r+\ln r≤0$, with equality only for $r=1$.

\smallskip\noindent
{\bf Proof:} The first derivative is positive if $r<1$, negative
if $r>1$.

\smallskip\noindent
{\bf Theorem B.} There is an unbounded increasing function $f(L)$,
for which if $S$ is an infinite sequence of random bits, the number
of prefixes~$S↓L$ of $S$ which have complexity $≤L+f(L)$ is
finite with probability~1. This strengthens a result of Chaitin,
who proved it true for constant~$f$.

\smallskip
The number $N↓L$ of strings of length $L$ which have {\sl low\/}
complexity $\bigl(<L+f(L)\bigr)$ is constrained by the fact that their
total probability is $\xleq P(L)\doteq 2↑{-C(L)}$. Since each
such string has probability $≥2↑{-\bigl(L+f(L)\bigr)}$,
$N↓L\xleq 2↑{-C(L)}/2↑{-\bigl(L+f(L)\bigr)}=
2↑{L+f(L)-C(L)}$. Let $F↓L$ be the fraction which have low
complexity; $F↓L=N↓L\cdot 2↑{-L}\xleq 2↑{f(L)-C(L)}\xeq 2↑{f(L)}\cdot P(L)$.
The expected number of low complexity~$S↓L$ of all lengths is
$\sum F↓L\xleq\sum↓L 2↑{f(L)}\cdot P(L)$. The probability that $S↓L$
has $\xgeq k\sum F↓L$ low complexity prefixes is at most~$1/k$, so
if $\sum F↓L$ is finite this probability approaches zero, and $S$
has only finitely many low complexity prefixes with probability~1.
It remains to pick the right $f(L)$ to keep $\sum↓L2↑{f(L)}\cdot P(L)$
finite. Equivalently, letting $g(L)=2↑{f(L)}$, we need to find a
power-of-2-valued unbounded nondecreasing function $g(L)$ for which
$\sum↓Lg(L)P(L)$ is finite. We temporarily relax the
power-of-2 requirement; if we meet the other requirements on~$g$, we
can easily adjust it by rounding up to the next higher power of~2.

Let $Q(L)=\sum↓{i=L}↑∞P(i)$; $0<Q(L)<1$, and $Q(L)$ decreases
with limit~$=0$; $P(L)=Q(L)-Q(L+1)$. We want to make finite the sum
$$\eqalign{\sum↓Lg(L)P(L)&=\sum↓Lg(L)\bigl(Q(L)-Q(L+1)\bigr)\cr
\noalign{\smallskip}
&=\sum↓Lg(L)Q(L)-\sum↓Lg(L-1)Q(L)\cr
\noalign{\smallskip}
&=\sum↓L\bigl(g(L)-g(L-1)\bigr)Q(L)\,.\cr}$$
The intuitive idea is to start $g$ out at zero, and increase it by 1
whenever $Q$ drops by a factor of~2. The rigorous proof works
best by letting $g(L)=-\ln Q(L)$. We prove, by induction on~$L$,
$$\sum↓{i<L}\bigl(g(i)-g(i-1)\bigr)Q(L)≤1-Q(L)<1\,.$$
The basis $L=0$ is trivial, and the induction step requires that
$$Q(L+1)-Q(L)+\bigl(\ln Q(L)-\ln Q(L+1)\bigr) Q(L+1)≤0\,,$$
or
$$1-{Q(L)\over Q(L+1)}+\ln \biggl({Q(L)\over Q(L+1)}\biggr)≤0\,,$$
a special case of the elementary $1-r+\ln r≤0$. Working back, we see
that $g(L)$ is the next power of 2 above $-\ln\sum↓{i≥L}P(i)$, and
$f(L)=\lg\bigl(g(L)\bigr)$, so $f$ is $\lfloor\lg\bigl(-\ln\sum↓{i≥L}P(i)
\bigr)\rfloor$.

A property of infinite bit sequences is a {\sl measure 1 property\/}
if all sequences but a set of measure zero have the property.

\smallskip
Examples: The sequence contains a 1; the fraction of 1's approaches
1/2; every bit pattern appears somewhere (?); the sequence is not
a recursive function; it is not the range of a recursive function, etc.

\smallskip\noindent
{\bf Conjecture:} The conjunction of a countable set of measure 1
properties is a measure 1 property.

\smallskip\noindent
{\bf Definition:} A sequence is {\sl random\/} if it has all ``mathematically
definable'' measure 1 properties.

\smallskip
Open question: Is $P↓H(U)$ random in this sense? Is it random in the
sense of Theorem~B? It is random in the sense of Chaitin's weak
form of Theorem~B.

\smallskip
Theorem B can be restated to apply to the prefixes of random finite
strings of a given length. The probability that more than $k$
of the prefixes of such a string have low complexity is at most~$1/k$.

Theorem B states a measure-1 property. It can be taken as providing
an intrinsic definition of randomness for infinite sequences. A~sequence
which is actually random meets the definition with probability~1,
while one which meets any of the usual criteria of non-randomness
fails with probability~1.

\vfill\eject\end